package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * 1022. 从根到叶的二进制数之和
 * @author feizns
 * @since 2020/1/7
 */
public class SumRootToLeaf {

    public static void main(String[] args) {
        System.out.println(sumRootToLeaf(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.right = new TreeNode(0);
        return ret;
    }

    static List<String> list = new ArrayList<>();

    public static int sumRootToLeaf(TreeNode root) {
        return root == null ? 0 : sumRootToLeaf(root, 0);
    }

    public static int sumRootToLeaf(TreeNode root, int sum) {
        sum = sum * 2 + root.val;
        if ( root.left == null && root.right == null )
            return sum;
        else if ( root.left == null )
            return sumRootToLeaf(root.right, sum);
        else if ( root.right == null )
            return sumRootToLeaf(root.left, sum);
        else
            return sumRootToLeaf(root.left, sum) + sumRootToLeaf(root.right, sum);
    }

}
